#!/usr/bin/env ruby
require 'rubygems'
require 'gnuplot'

class Point
  attr_reader :x, :y

  def initialize(x, y)
    @x = x
    @y = y
  end
  
  def distance(point)
    Math.sqrt((@x - point.x)**2 + (@y - point.y)**2)
  end

  def to_s
    "#{x}, #{y}"
  end

  def to_gplot
    "#{x} #{y}"
  end
end

class Cluster < Array
  attr_accessor :centroid
  attr_accessor :data

  def initialize(centroid)
    @centroid = centroid
    super()
  end

  def update_centroid
    old_centroid = @centroid
    #puts "Cluster size: %d" % self.size
    i = 0
    true_center = Point.new(
                          self.inject(0){|s,v| puts i+=1; s + v.x} / Float(self.size),
                          self.inject(0){|s,v| s + v.y} / Float(self.size))
    @centroid = self.min {|a,b| a.distance(true_center) <=> b.distance(true_center)}

    return (not (old_centroid == @centroid))
  end

  def distance(cluster)
    @centroid.distance(cluster.centroid)
  end

  def merge(cluster)
    self << cluster.data
    update_centroid
  end
end

class KClusterer
  attr_reader :clusters

  def initialize(dataset, k)
    @data = dataset
    @num_clusters = k
    @clusters = []
  end
end

# Not working quite yet...
class Agglomerative < KClusterer
  def run
    @clusters = @data.map {|item| c = Cluster.new(item); c << item }
    return self if @clusters.size <= 2

    while(@clusters.size > @num_clusters) 
      pair = nil
      min = Float::MAX
      @clusters.each { |a| @clusters.each {|b| pair = [a, b] if a.distance(b) < min }}

      pair[0].merge(@clusters.delete(pair[1]))
    end

    self
  end
end

class Kmeans < KClusterer
  def run
    centroid_indices = []

    # Random seeding
    @num_clusters.times do
      c = nil
      loop do
        c = rand(@data.size)
        break unless centroid_indices.include?(c)
      end

      centroid_indices << c
      @clusters << Cluster.new(@data[c].clone)
    end

    loop do
      # Put each data item into the cluster whose center it is closest too.
      @data.each do |item|
        @clusters.min {|a, b| a.centroid.distance(item) <=> b.centroid.distance(item) } << item
      end

      break unless @clusters.map {|c| c.update_centroid }.detect {|i| i}
    end

    self
  end
end

points = [
  Point.new(1,1),
  Point.new(3,3),
  Point.new(2,2),
  Point.new(3,1),
  Point.new(1,3),
  Point.new(-1,-1),
  Point.new(-3,-3),
  Point.new(-2,-2),
  Point.new(-3,-1),
  Point.new(-1,-3)
]

km = Kmeans.new(points, 2).run
km.clusters.each {|c| puts c.centroid}

#ag = Agglomerative.new(points, 2).run
#ag.clusters.each {|c| puts c.centroid}

x = points.collect {|p| p.x}
y = points.collect {|p| p.y}

Gnuplot.open do |gp|
  Gnuplot::Plot.new( gp ) do |plot|
  
    plot.title  "Array Plot Example"
    plot.ylabel "x"
    plot.xlabel "x^2"
    
#    x = (0..50).collect { |v| v.to_f }
#    y = x.collect { |v| v ** 2 }

    plot.data << Gnuplot::DataSet.new([x,y]) do |ds|
      ds.with = "points palette"
      ds.notitle
    end

    x2 = x.clone.each {|i| 
    y2 = y.clone
    plot.data << Gnuplot::DataSet.new([x2,y2]) do |ds|
      ds.with = "points palette"
      ds.notitle
    end
  end
end
